class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder,int& preindex,vector<int>& inorder,int inrbegin,int inend)
    {
        if(inrbegin>inend||preindex>=preorder.size())
        {
            return nullptr;
        }//说明这不是一个正常的子区间,或者已经递归完成了
        //寻找左子树和右子树的确认范围
        TreeNode* node = new TreeNode(preorder[preindex]);//确定了根节点
        int j = inrbegin;
        while(j<=inend)
        {
            if(inorder[j] == preorder[preindex])
            {
                break;
            }
            j++;
        }
        preindex++;
        //确定了左右子树的范围，再去构建左右子树的根节点
        node->left = _buildTree(preorder,preindex,inorder,inrbegin,j-1);//构建左子树
        node->right = _buildTree(preorder,preindex,inorder,j+1,inend);//构建右子树
        return node;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 这道题目的解法就是通过先序遍历确定根节点，然后通过中序遍历确定根节点的左右子树的值范围，
        // 再通过先序遍历确定该节点左子树的根节点，以及右子树的根节点，再将左右子树当做根节点去进行处理即可
        // 最小字问题就是每一层的节点都要通过先序遍历知道我的值是多少然后进行构建，然后通过中序遍历知道我的
        // 左子树的值范围，和我右子树的值范围。递归去处理左子树和右子树，使用的是先序遍历的思想
        int i = 0;
        return  _buildTree(preorder,i,inorder,0,inorder.size()-1);//第一层根节点的位置就是先序遍历的0节点

    }
};